A BBC correspondent in the Democratic Republic of the Congo capital, Kinshasa, says that crowds of angry students have set UN vehicles on fire.
They say UN peacekeepers should have prevented the rebel advance, which casts doubts on last year's peace deal.
However, the rebel leader says that his forces will now leave the town.
DR Congo President Joseph Kabila has said Bukavu was "under the control of Rwandan occupants", and told the BBC it was "a situation of war".
Rwanda has denied any involvement.
'Persecution'
UN troops had fired tear gas at demonstrators in Kinshasa, said UN spokesman Hamadoun Toure.
There were also reports of anti-UN protests in Bukavu, Kisangani and Kindu.
Rebel leader Brig Gen Laurent Nkunda said that he had already ordered 300 fighters to leave and the rest would depart later on Thursday.
"We shall withdraw to reorganisation centres to assure the transitional government that we are not opposed to it," he said.
"We are just opposed to the persecution of one section of the Congolese community."
Additional UN peacekeepers were sent to Bukavu last week, following fighting between the dissidents and regular troops.
But the 1,000-strong UN force did not oppose the advancing rebel fighters, saying it did not have a mandate to "make war".
'Genocide'
The dissidents are from a former Rwanda-backed rebel group, that was supposed to join the national army.
Gen Nkunda and other renegade commanders - ethnic Banyamulenges, related to Rwandan Tutsis - say government forces have been attacking members of their community.
In the capital Kinshasa, President Kabila on Wednesday said: "It is clearly an attack on our country by Rwandan troops.
"The army is mobilising with the objective of retaking control of Bukavu."
The UN said Rwandan troops had been spotted in DR Congo north of Bukavu six weeks ago, although they were all supposed to have left as part of last year's peace deal.
While Rwanda has denied having any troops in DR Congo, Foreign Minister Charles Muligande said that Rwanda would intervene to oppose "genocide".
Looting
Latest reports from the town speak of looting and rape, despite efforts by UN peacekeepers to maintain order.
Civilians looted two barges loaded with 300 tonnes of food aid on Wednesday, said Ndeley Agbaw, head of the World Food Programme office in Bukavu.
UN officials say that Gen Nkunda has at least 2,000 men under his control - up from 500 just two weeks ago.
They are reinforcing Col Jules Mutebusi, whose militia first clashed with the army last week.
A week of clashes has left at least 65 people dead, and thousands of Banyamulenge have fled into Rwanda.
Both Col Mutebusi and Gen Nkunda are former members of the largest rebel group, the RCD, which controlled all of eastern DR Congo during the five-year war.
Under a peace deal agreed last year, all the Congolese warring factions were supposed to unite as a single army, but progress has been slow.
Is this the end of peace in DR Congo? Should the UN have stopped the rebel advance? If you are in Bukavu, send us your experiences.
Your comments
My father's in Kinshasa at the moment. The rioting is very near where he is and it's sounding very dangerous indeed. The UN is a disgrace and always has been with regard to this conflict torn country. It sickens me.
Will, London, UK
I am living in Lubumbashi, DRC. Here there were also attacks on UN offices and eye witness reports say there have been gates broken down and general destruction especially by local students. Listening to people around me they are very unhappy that foreigners are getting paid big salaries for working for Monuc and not getting involved to stop the invasion of Bukavo.
Erika, Lubumbashi, DRC